πŸ‘©β€πŸ’» 42891. λ¬΄μ§€μ˜ λ¨Ήλ°© 라이브

@Seongukbaek Posted June 04, 2022 Β· Updated June 04, 2022 Β· 3 min read

문제

Programmers - λ¬΄μ§€μ˜ λ¨Ήλ°© 라이브

πŸ“ Logic

while (totalTime + ((pq.peek().time - prevTime) * len) <= k) { int now = pq.poll().time; totalTime += (now - prevTime) * len; len -= 1; prevTime = now; }
  • ν˜„μž¬ μŒμ‹μ„ 먹을 수 μžˆλ‹€λ©΄, Queue μ—μ„œ μ œμ™Έν•˜κ³  전체 μŒμ‹ 먹은 μ‹œκ°„μ„ μ¦κ°€μ‹œν‚¨λ‹€.
  • ν˜„μž¬ μŒμ‹μ„ 먹을 수 μ—†λŠ” κ²½μš°κΉŒμ§€ 이λ₯Ό λ°˜λ³΅ν•˜κ³ , 이후 totalTime κ³Ό 남은 μŒμ‹ 개수 len 을 μ΄μš©ν•˜μ—¬ 방솑 쀑단 이후 먹을 μŒμ‹μ„ μ°ΎλŠ”λ‹€.

πŸ“„ CODE

μ½”λ“œ 보기/μ ‘κΈ°πŸ’«
import java.util.*; class Food implements Comparable<Food> { int time; int idx; public Food(int time, int idx) { this.time = time; this.idx = idx; } @Override public int compareTo(Food f) { return this.time - f.time; } } class Solution { public int solution(int[] food_times, long k) { Queue<Food> pq = new PriorityQueue<>(); // λͺ¨λ“  μŒμ‹μ„ λ¨ΉλŠ”λ° κ±Έλ¦¬λŠ” 총 μ‹œκ°„ long foodSum = 0; int len = food_times.length; for (int i = 0; i < len; i++) { pq.add(new Food(food_times[i], i)); foodSum += food_times[i]; } // μŒμ‹μ„ λ‹€ μ„­μ·¨ν–ˆλŠ”λ° 아직 Kμ΄ˆκ°€ λ˜μ§€ μ•Šμ•˜λ‹€λ©΄ -1 λ°˜ν™˜ if (foodSum <= k) return -1; // λ¨ΉλŠ”λ° μ‚¬μš©ν•œ μ‹œκ°„ long totalTime = 0; // 직전에 λ‹€ 먹은 μŒμ‹ μ‹œκ°„ long prevTime = 0; // ν˜„μž¬ μŒμ‹μ„ 먹을 수 μžˆλŠ” 경우, totalTime을 증가 while (totalTime + ((pq.peek().time - prevTime) * len) <= k) { int now = pq.poll().time; totalTime += (now - prevTime) * len; len -= 1; prevTime = now; } ArrayList<Food> remainFoods = new ArrayList<>(); while (!pq.isEmpty()) remainFoods.add(pq.poll()); // idxλ₯Ό κΈ°μ€€μœΌλ‘œ μ˜€λ¦„μ°¨μˆœ μ •λ ¬ remainFoods.sort(Comparator.comparingInt(o -> o.idx)); return remainFoods.get((int) ((k - totalTime) % len)).idx + 1; } }

✏️ Review

  • μ²˜μŒμ—” K 와 μŒμ‹ 개수λ₯Ό μ΄μš©ν•΄ 각 μŒμ‹μ΄ K 초 이후 λ‚¨μ•„μžˆλŠ” 양을 κ³„μ‚°ν•˜μ—¬ λͺ‡ 번째 μŒμ‹μ„ 먹을지 κ²°μ •ν•˜λŠ” 방식을 νƒν–ˆλŠ”λ°, 잘λͺ»λœ μ ‘κ·Όλ²•μ΄μ—ˆλ‹€.
  • μ°Έκ³ λ₯Ό ν•˜λ‹ˆ "μŒμ‹λŸ‰μ΄ 적은 것을 λ‹€ 먹게 λœλ‹€λ©΄ μ–΄μ°¨ν”Ό κ·Έ 보닀 μŒμ‹λŸ‰μ΄ 큰 것듀도 이미 λ‹€ 먹은 μŒμ‹λ§ŒνΌ 먹게 λ˜λŠ” 점"을 μ΄μš©ν•œ 접근법을 μ‚¬μš©ν–ˆμ—ˆλ‹€.

    • 이 말이 잘 μ΄ν•΄λ˜μ§€ μ•Šμ•„ μ‹œκ°„μ΄ κ±Έλ Έλ‹€.
@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€